package com.lenl.arithmetic.huffmancode;


import java.io.*;
import java.util.*;

/**
 * @author Lenl
 * @version v1.0
 * @create 2022-05-10 11:15
 * @description 赫夫曼压缩编码
 */
public class HuffmanCode {
    public static void main(String[] args) {
        String content="i like like like java do you like a java hello world";
        byte[] contentBytes=content.getBytes();
        System.out.println(contentBytes.length);

        /*
        List<Node> nodes= getNodes(contentBytes);
        System.out.println(nodes);
        //创建二叉树
        System.out.println("赫夫曼树：");
        Node huffmanTreeRoot=createHuffmanTree(nodes);
        preOrder(huffmanTreeRoot);
        //测试生成的赫夫曼编码
        Map<Byte,String> huffmanCodes= getCodes(huffmanTreeRoot);
        System.out.println("生成的赫夫曼编码表："+huffmanCodes);

        byte[] huffmanCodeBytes= zip(contentBytes,huffmanCodes);
        System.out.println("huffmanCodeBytes="+Arrays.toString(huffmanCodeBytes));
         */
        //封装后的调用
        byte[] huffmanCodeBytes=huffmanZip(contentBytes);
        //System.out.println("压缩后的结果："+Arrays.toString(huffmanCodeBytes)+"，长度为"+huffmanCodeBytes.length);

        byte[] source= decode(huffmanCodes,huffmanCodeBytes);
        System.out.println("解码后："+new String(source));

        //测试压缩文件
        String srcFile="E:\\项目学习\\算法与数据结构\\Code\\Source\\1.jpg";
        String destFile="E:\\项目学习\\算法与数据结构\\Code\\Source\\dst.zip";
        //zipFile(srcFile,destFile);
        //System.out.println("已完成压缩。");

        //解压缩文件
        String unzipDestFile="E:\\项目学习\\算法与数据结构\\Code\\Source\\unzip.jpg";
        unZipFile(destFile,unzipDestFile);
        System.out.println("解压完成");
    }

    //将一个文件进行压缩
    public static void zipFile(String srcFile,String destFile){
        FileInputStream is=null;
        FileOutputStream os=null;
        ObjectOutputStream oos=null;
        try {
            //创建输出流

            //从将建文件的输入流
            is=new FileInputStream(srcFile);
            //创建一个和源文件大小一样的byte[]
            byte[] b=new byte[is.available()];
            //读取文件
            is.read(b);
            //对源文件压缩
            byte[] huffmanBytes=huffmanZip(b);
            //创建文件的输出流，存放压缩文件
            os=new FileOutputStream(destFile);
            //创建一个和文件输出流相关联的objectOutputStream;
            oos=new ObjectOutputStream(os);
            //以对象流的方式写入字节数组和 赫夫曼编码 ，为了以后解压恢复源文件时使用
            oos.writeObject(huffmanBytes);
            oos.writeObject(huffmanCodes);
            oos.flush();

        } catch (Exception e) {
            System.out.println(e.getMessage());
            e.printStackTrace();
        }finally {
            try {
                if(is!=null)
                    is.close();
                if(oos!=null)
                    oos.close();
                if(os!=null)
                    os.close();
            } catch (IOException e) {
                System.out.println(e.getMessage());
                e.printStackTrace();
            }
        }

    }

    //文件解压缩
    public static void unZipFile(String zipFile,String destFile){
        FileInputStream is=null;
        ObjectInputStream ois=null;
        FileOutputStream os=null;
        try{
            is=new FileInputStream(zipFile);
            //和is关联的对象输入流
            ois=new ObjectInputStream(is);
            byte[] huffmanBytes=(byte[]) ois.readObject();
            //读取赫夫曼编码表
            Map<Byte,String> codes=(Map<Byte,String>)ois.readObject();
            //解码
            byte[] bytes=decode(codes,huffmanBytes);
            //写入新文件
            os=new FileOutputStream(destFile);
            os.write(bytes);
            os.flush();
        }catch (Exception e){
            System.out.println(e.getMessage());
        }finally {
            try{
                if(is!=null)
                    is.close();
                if(ois!=null)
                    ois.close();
                if(os!=null)
                    os.close();
            }catch (Exception e){
                System.out.println(e.getMessage());
            }
        }
    }






    //完成数据的解压
    //将huffmanCodeBytes转为对应二进制编码的字符串“101010000...”
    //将对应二进制编码重新转为字符串

    //完成压缩数据的解码

    /**
     *
     * @param huffmanCodes 赫夫曼编码表map
     * @param huffmanBytes 赫夫曼编码得到的字节数组
     * @return
     */
    private static byte[] decode(Map<Byte,String> huffmanCodes,byte[] huffmanBytes){
        //1.先得到huffmanBytes对应的二进制字符串
        StringBuilder stringBuilder=new StringBuilder();
        //将byte数组转为二进制的字符串
        for (int i=0;i<huffmanBytes.length;i++){
            boolean flag=(i==huffmanBytes.length-1);
            String str= byteToBitString(!flag,huffmanBytes[i]);
            stringBuilder.append(str);
        }
        //System.out.println("赫夫曼字节数组转对应二进制字符串："+stringBuilder.toString());

        //把赫夫曼编码进行掉换，构成反向查询的字典
        Map<String ,Byte> map=new HashMap<>();
        for (Map.Entry<Byte,String> entry:huffmanCodes.entrySet()){
            map.put(entry.getValue(), entry.getKey());
        }

        //创建集合，存放byte
        List<Byte> list=new ArrayList<>();
        for (int i=0;i<stringBuilder.length();i++){
            //扫描stringbuilder
            int count=1;
            boolean flag=true;
            Byte b=null;
            while(flag){
                //递增取出字符串
                String key=stringBuilder.substring(i,i+count);
                b=map.get(key);
                if(b==null)
                    count++;
                else
                    flag=false;
            }
            list.add(b);
            i+=count-1;
        }
        //结束后，list中存放了所有的字符
        byte[] b=new byte[list.size()];
        for (int i=0;i<b.length;i++){
            b[i]=list.get(i);
        }



        return b;
    }

    //将一个byte转为二进制的字符串
    /**
     *
     * @param flag true标识需要补高位，false表示不补（最后一位）
     * @param b 传入的byte
     * @return 对应二进制的字符串，按补码返回
     */
    private  static String byteToBitString(boolean flag, byte b){
        int temp=b;

        //正数要补位，负数要截取
        if(flag) //非最后一位，执行按位与
            temp |=256; //按位与 256 -> 10000 0000 1-> 0000 0001 => 1 0000 0001
        String re= Integer.toBinaryString(temp); //返回的是temp对应的二进制的补码

        if(flag||temp<0) //非最后一位且小于0就截取
            return re.substring(re.length()-8); //截取后8位
        else
            return re;
    }



    //封装赫夫曼压缩编码，便于直接调用
    /**
     *
     * @param bytes  要压缩的字符串字节数组
     * @return 经过赫夫曼编码压缩后的数组
     */
    private  static  byte[] huffmanZip(byte[] bytes){
        List<Node> nodes= getNodes(bytes);
        //根据nodes创建赫夫曼树
        Node huffmanTreeRoot=createHuffmanTree(nodes);
        //对应的赫夫曼编码
        Map<Byte,String> huffmanCodes=getCodes(huffmanTreeRoot);
        //根据生成的赫夫曼编码，压缩得到压缩后的赫夫曼编码字节数组
        byte[] huffmanCodeBytes=zip(bytes,huffmanCodes);
        return huffmanCodeBytes;
    }


    //编写方法，将字符串对应的byte[]数组，通过生成的赫夫曼编码表，返回赫夫曼压缩后的byte[]
    private  static byte[] zip(byte[] bytes,Map<Byte,String> huffmanCodes){
        //1.利用huffmanCodes将bytes转成赫夫曼编码对应的字符串
        StringBuilder stringBuilder=new StringBuilder();
        //遍历byte[]数组
        for (byte b:bytes){
            stringBuilder.append(huffmanCodes.get(b));
        }
        //System.out.println("测试原二进制字符串："+stringBuilder.toString());
        //将字符串转成byte[]数组
        //统计返回的返回的byte[]的length
        int len=(stringBuilder.length()+7)/8;
        //创建存储压缩后的byte数组
        byte[] huffmanCodeBytes=new byte[len];
        int index=0;//记录第几个byte
        for (int i=0;i<stringBuilder.length();i+=8){
            //每8位对应一个byte，所以步长为8
            String strByte;
            if(i+8>stringBuilder.length()){
                strByte=stringBuilder.substring(i);
            }else{
                strByte=stringBuilder.substring(i,i+8);
            }
            //将strByte转为byte，放入huffmanCodeBytes
            huffmanCodeBytes[index]=(byte)Integer.parseInt(strByte,2);
            index++;
        }
        return huffmanCodeBytes;
    }


    //生成赫夫曼树对应的赫夫曼编码
    //存储在Map<Byte,String>中
    static Map<Byte,String> huffmanCodes=new HashMap<>();
    //需要去拼接路径 使用 StringBuilder,存储叶子节点的路径
    static StringBuilder stringBuilder=new StringBuilder();

    /**
     * 将传入的node节点的所有叶子节点的赫夫曼编码得到，并存入Map中
     * @param node 树根节点
     * @param code 路径：左子节点为0，右子节点为1
     * @param stringBuilder 用于拼接code
     */
    private static void getCodes(Node node,String code,StringBuilder stringBuilder){
        StringBuilder stringBuilder2=new StringBuilder(stringBuilder);
        //将code加入到stringbuilder2
        stringBuilder2.append(code);
        if(node!=null){
            //判断当前node是叶子节点还是非叶子节点
            if(node.data==null){
                //非叶子节点
                //向左
                getCodes(node.left,"0",stringBuilder2);
                //向右
                getCodes(node.right,"1",stringBuilder2);
            }else{
                //说明是叶子节点
                //找到了某个叶子节点的最后
                huffmanCodes.put(node.data,stringBuilder2.toString());
            }
        }
    }

    //为调用方面，重载getCodes
    private  static Map<Byte,String> getCodes(Node root){
        if(root==null)
            return null;
        getCodes(root.left,"0",stringBuilder);
        getCodes(root.right,"1",stringBuilder);
        return huffmanCodes;
    }

    //前序遍历
    private  static  void preOrder(Node root){
        if(root!=null){
            root.preOrder();
        }else{
            System.out.println("树为空，不能遍历。");
        }
    }

    //接受一个字节数组，返回值和次数的Node的list
    private static List<Node> getNodes(byte[] bytes){
        //创建ArrayList
        ArrayList<Node> nodes=new ArrayList<>();
        //遍历bytes存储每个byte出现的次数 map
        HashMap<Byte,Integer> counts=new HashMap<>();
        for(byte b:bytes){
            Integer count=counts.get(b);
            if(count==null){
                counts.put(b,1);
            }else{
                counts.put(b,count+1);
            }
        }
        //把每个键值对转成Node对象，并加入nodes
        //遍历map
        for (Map.Entry<Byte,Integer> entry:counts.entrySet()){
            nodes.add(new Node(entry.getKey(),entry.getValue()));
        }
        return nodes;
    }

    //通过List创建对应的赫夫曼树
    private  static Node createHuffmanTree(List<Node> nodes){
        while(nodes.size()>1){
            //排序，从小到大
            Collections.sort(nodes);
            //取出第一棵最小二叉树
            Node leftNode=nodes.get(0);
            //取出第二棵
            Node rightNode=nodes.get(1);
            //创建一颗新的二叉树，根节点只有权值weight没有data
            Node parent=new Node(null,leftNode.weight+rightNode.weight);
            parent.left=leftNode;
            parent.right=rightNode;
            //将已处理的二叉树移除
            nodes.remove(leftNode);
            nodes.remove(rightNode);
            //新的二叉树加入
            nodes.add(parent);
        }
        //nodes中最后的节点就是赫夫曼树的根节点
        return nodes.get(0);
    }


}

//创建Node，存储数据和权值
class Node implements Comparable<Node>{
    Byte data;//存放数据本身
    int weight;//权值
    Node left;
    Node right;
    public Node(Byte data,int weight){
        this.data=data;
        this.weight=weight;
    }

    @Override
    public int compareTo(Node o){
        //顺序排序
        return this.weight-o.weight;
    }

    @Override
    public String toString(){
        return "Node [data="+data+" weight="+weight+"]";
    }

    //前序遍历
    public  void preOrder(){
        System.out.println(this);
        if(this.left!=null)
            this.left.preOrder();
        if(this.right!=null)
            this.right.preOrder();
    }

}